package primary.code02_Sort;

import java.util.Arrays;

/**
 * 荷兰国旗问题，三色问题
 */
public class Code04_Partition {

    /**
     * 根据 num 对 arr 在 l ~ r 范围内划分
     */
    private static void partition(int[] arr, int l, int r, int num) {
        if (arr == null || arr.length == 1) return;
        int p1 = -1;
        int p2 = arr.length;
        int i = 0;
        while (i != p2) {
            if (arr[i] < num) {
                swap(arr, i, p1 + 1);
                p1++;
                i++;
            } else if (arr[i] == num) {
                i++;
            } else {
                swap(arr, i, p2 - 1);
                p2--;
            }
        }
    }

    private static void partitionTest(int[] arr, int l, int r, int num) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int pl = l - 1;
        int pg = r + 1;
        int i = l;
        while (i < pg) {
            if (arr[i] < num) {
                swap(arr, ++pl, i++);
            } else if (arr[i] > num) {
                swap(arr, --pg, i);
            } else {
                i++;
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        if (i == j) return;
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

    public static void main(String[] args) {
        int[] arr = {34, 7, 4, 7, 4, 23, 48, 48, 23, 23, 23};
        partitionTest(arr, 0, arr.length - 1, 23);
//        partition(arr, 0, arr.length - 1, 23);
        //[7, 4, 7, 4, 23, 23, 23, 23, 48, 48, 34]
        System.out.println(Arrays.toString(arr));
    }
}
